home *** CD-ROM | disk | FTP | other *** search
/ Windows Expert / Windows Expert.iso / windownt / grep16.zip / GREP.C < prev    next >
C/C++ Source or Header  |  1993-02-25  |  27KB  |  1,010 lines
  1. /* grep - print lines matching an extended regular expression
  2.    Copyright (C) 1988 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18. /* Written June, 1988 by Mike Haertel
  19.    BMG speedups added July, 1988 by James A. Woods and Arthur David Olson  */
  20.  
  21. #include <stdio.h>
  22. #include <io.h>
  23. #undef eof
  24.  
  25. #if defined(USG) || defined(STDC_HEADERS)
  26. #include <string.h>
  27. #ifndef bcopy
  28. #define bcopy(s,d,n)    memcpy((d),(s),(n))
  29. #endif
  30. #ifndef index
  31. #define index strchr
  32. #endif
  33. #else
  34. #include <strings.h>
  35. #endif
  36.  
  37. #ifdef HAVE_UNISTD_H
  38. #include <unistd.h>
  39. #endif
  40.  
  41. #ifndef STDC_HEADERS
  42. extern char *getenv();
  43. #endif
  44. extern int errno;
  45.  
  46. extern char *sys_errlist[];
  47.  
  48. #include "dfa.h"
  49. #include "regex.h"
  50. #include "getopt.h"
  51.  
  52. /* Used by -w */
  53. #define WCHAR(C) (ISALNUM(C) || (C) == '_')
  54.  
  55. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  56.  
  57. /* Exit status codes. */
  58. #define MATCHES_FOUND 0        /* Exit 0 if no errors and matches found. */
  59. #define NO_MATCHES_FOUND 1    /* Exit 1 if no matches were found. */
  60. #define ERROR 2            /* Exit 2 if some error occurred. */
  61.  
  62. /* Error is set true if something awful happened. */
  63. static int error;
  64.  
  65. /* The program name for error messages. */
  66. static char *prog;
  67.  
  68. /* We do all our own buffering by hand for efficiency. */
  69. static char *buffer;        /* The buffer itself, grown as needed. */
  70. static bufbytes;        /* Number of bytes in the buffer. */
  71. static size_t bufalloc;        /* Number of bytes allocated to the buffer. */
  72. static bufprev;            /* Number of bytes that have been forgotten.
  73.                    This is used to get byte offsets from the
  74.                    beginning of the file. */
  75. static bufread;            /* Number of bytes to get with each read(). */
  76.  
  77. static void
  78. initialize_buffer()
  79. {
  80.   bufread = 8192;
  81.   bufalloc = bufread + bufread / 2;
  82.   buffer = malloc(bufalloc);
  83.   if (! buffer)
  84.     {
  85.       fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  86.           sys_errlist[errno]);
  87.       exit(ERROR);
  88.     }
  89. }
  90.  
  91. /* The current input file. */
  92. static fd;
  93. static char *filename;
  94. static eof;
  95.  
  96. /* Fill the buffer retaining the last n bytes at the beginning of the
  97.    newly filled buffer (for backward context).  Returns the number of new
  98.    bytes read from disk. */
  99. static int
  100. fill_buffer_retaining(n)
  101.      int n;
  102. {
  103.   char *p, *q;
  104.   int i;
  105.  
  106.   /* See if we need to grow the buffer. */
  107.   if (bufalloc - n <= bufread)
  108.     {
  109.       while (bufalloc - n <= bufread)
  110.     {
  111.       bufalloc *= 2;
  112.       bufread *= 2;
  113.     }
  114.       buffer = realloc(buffer, bufalloc);
  115.       if (! buffer)
  116.     {
  117.       fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  118.           sys_errlist[errno]);
  119.       exit(ERROR);
  120.     }
  121.     }
  122.  
  123.   bufprev += bufbytes - n;
  124.  
  125.   /* Shift stuff down. */
  126.   for (i = n, p = buffer, q = p + bufbytes - n; i--; )
  127.     *p++ = *q++;
  128.   bufbytes = n;
  129.  
  130.   if (eof)
  131.     return 0;
  132.  
  133.   /* Read in new stuff. */
  134.   i = read(fd, buffer + bufbytes, bufread);
  135.   if (i < 0)
  136.     {
  137.       fprintf(stderr, "%s: read on %s failed (%s)\n", prog,
  138.           filename ? filename : "<stdin>", sys_errlist[errno]);
  139.       error = 1;
  140.     }
  141.  
  142.   /* Kludge to pretend every nonempty file ends with a newline. */
  143.   if (i == 0 && bufbytes > 0 && buffer[bufbytes - 1] != '\n')
  144.     {
  145.       eof = i = 1;
  146.       buffer[bufbytes] = '\n';
  147.     }
  148.  
  149.   bufbytes += i;
  150.   return i;
  151. }
  152.  
  153. /* Various flags set according to the argument switches. */
  154. static trailing_context;    /* Lines of context to show after matches. */
  155. static leading_context;        /* Lines of context to show before matches. */
  156. static byte_count;        /* Precede output lines the byte count of the
  157.                    first character on the line. */
  158. static no_filenames;        /* Do not display filenames. */
  159. static line_numbers;        /* Precede output lines with line numbers. */
  160. static silent;            /* Produce no output at all.  This switch
  161.                    is bogus, ever hear of /dev/null? */
  162. static int whole_word;        /* Match only whole words.  Note that if
  163.                    backreferences are used this depends on
  164.                    the regex routines getting leftmost-longest
  165.                    right, which they don't right now if |
  166.                    is also used. */
  167. static int whole_line;        /* Match only whole lines.  Backreference
  168.                    caveat applies here too.  */
  169. static nonmatching_lines;    /* Print lines that don't match the regexp. */
  170.  
  171. static bmgexec;            /* Invoke Boyer-Moore-Gosper routines */
  172.  
  173. /* The compiled regular expression lives here. */
  174. static struct regexp reg;
  175.  
  176. /* The compiled regular expression for the backtracking matcher lives here. */
  177. static struct re_pattern_buffer regex;
  178.  
  179. /* Pointer in the buffer after the last character printed. */
  180. static char *printed_limit;
  181.  
  182. /* True when printed_limit has been artifically advanced without printing
  183.    anything. */
  184. static int printed_limit_fake;
  185.  
  186. /* Print a line at the given line number, returning the number of
  187.    characters actually printed.  Matching is true if the line is to
  188.    be considered a "matching line".  This is only meaningful if
  189.    surrounding context is turned on. */
  190. static int
  191. print_line(p, number, matching)
  192.      char *p;
  193.      int number;
  194.      int matching;
  195. {
  196.   int count = 0;
  197.  
  198.   if (silent)
  199.     {
  200.       do
  201.     ++count;
  202.       while (*p++ != '\n');
  203.       printed_limit_fake = 0;
  204.       printed_limit = p;
  205.       return count;
  206.     }
  207.  
  208.   if (filename && !no_filenames)
  209.     printf("%s%c", filename, matching ? ':' : '-');
  210.   if (byte_count)
  211.     printf("%d%c", p - buffer + bufprev, matching ? ':' : '-');
  212.   if (line_numbers)
  213.     printf("%d%c", number, matching ? ':' : '-');
  214.   do
  215.     {
  216.       ++count;
  217.       putchar(*p);
  218.     }
  219.   while (*p++ != '\n');
  220.   printed_limit_fake = 0;
  221.   printed_limit = p;
  222.   return count;
  223. }
  224.  
  225. /* Print matching or nonmatching lines from the current file.  Returns a
  226.    count of matching or nonmatching lines. */
  227. static int
  228. grep()
  229. {
  230.   int retain = 0;        /* Number of bytes to retain on next call
  231.                    to fill_buffer_retaining(). */
  232.   char *search_limit;        /* Pointer to the character after the last
  233.                    newline in the buffer. */
  234.   char saved_char;        /* Character after the last newline. */
  235.   char *resume;            /* Pointer to where to resume search. */
  236.   int resume_index = 0;        /* Count of characters to ignore after
  237.                    refilling the buffer. */
  238.   int line_count = 1;        /* Line number. */
  239.   int try_backref;        /* Set to true if we need to verify the
  240.                    match with a backtracking matcher. */
  241.   int initial_line_count;    /* Line count at beginning of last search. */
  242.   char *match;            /* Pointer to the first character after the
  243.                    string matching the regexp. */
  244.   int match_count = 0;        /* Count of matching lines. */
  245.   char *matching_line;        /* Pointer to first character of the matching
  246.                    line, or of the first line of context to
  247.                    print if context is turned on. */
  248.   char *real_matching_line;    /* Pointer to the first character of the
  249.                    real matching line. */
  250.   char *next_line;        /* Pointer to first character of the line
  251.                    following the matching line. */
  252.   char *last_match_limit;    /* Pointer after last matched line. */
  253.   int pending_lines = 0;    /* Lines of context left over from last match
  254.                    that we have to print. */
  255.   static first_match = 1;    /* True when nothing has been printed. */
  256.   int i;
  257.   char *tmp;
  258.   char *execute();
  259.  
  260.   printed_limit_fake = 0;
  261.   
  262.   while (fill_buffer_retaining(retain) > 0)
  263.     {
  264.       /* Find the last newline in the buffer. */
  265.       search_limit = buffer + bufbytes;
  266.       while (search_limit > buffer && search_limit[-1] != '\n')
  267.     --search_limit;
  268.       if (search_limit == buffer)
  269.     {
  270.       retain = bufbytes;
  271.       continue;
  272.     }
  273.  
  274.       /* Save the character after the last newline so regexecute can write
  275.      its own sentinel newline. */
  276.       saved_char = *search_limit;
  277.  
  278.       /* Search the buffer for a match. */
  279.       printed_limit = buffer;
  280.       resume = buffer + resume_index;
  281.       last_match_limit = resume;
  282.       initial_line_count = line_count;
  283.  
  284.  
  285.       /* In retrospect, I have to say that the following code sucks.
  286.      For an example of how to do this right, see the fgrep
  287.      driver program that I wrote around a year later.  I'm
  288.      too lazy to retrofit that to egrep right now (the
  289.      pattern matchers have different needs).  */
  290.  
  291.  
  292.       while (match = execute(®, resume, search_limit, 0, &line_count, &try_backref))
  293.     {
  294.       /* Find the beginning of the matching line. */
  295.       matching_line = match;
  296.       while (matching_line > resume && matching_line[-1] != '\n')
  297.         --matching_line;
  298.       real_matching_line = matching_line;
  299.  
  300.       /* Find the beginning of the next line. */
  301.       next_line = match;
  302.       while (next_line < search_limit && *next_line++ != '\n')
  303.         ;
  304.  
  305.       /* If a potential backreference is indicated, try it out with
  306.          a backtracking matcher to make sure the line is a match.
  307.          This is hairy because we need to handle whole_line and
  308.          whole_word matches specially.  The method was stolen from
  309.          GNU fgrep.  */
  310.       if (try_backref)
  311.         {
  312.           struct re_registers regs;
  313.           int beg, len, maxlen, ret;
  314.  
  315.           beg = 0;
  316.           for (maxlen = next_line - matching_line - 1; beg <= maxlen; ++beg)
  317.         {
  318.           /* See if the matching line matches when backreferences
  319.              are considered... */
  320.           ret = re_search (®ex, matching_line, maxlen,
  321.                    beg, maxlen - beg, ®s);
  322.           if (ret == -1)
  323.             goto fail;
  324.           beg = ret;
  325.           len = regs.end[0] - beg;
  326.           /* Ok, now check if it subsumed the whole line if -x */
  327.           if (whole_line && (beg != 0 || len != maxlen))
  328.             goto fail;
  329.           /* If -w then check if the match aligns with word
  330.              boundaries.  We have to do this iteratively, because
  331.              (a) The line may contain more than one occurence
  332.              of the pattern, and;
  333.              (b) Several alternatives in the pattern might
  334.              be valid at a given point, and we may need to
  335.              consider a shorter one in order to align with
  336.              word boundaries.  */
  337.           else if (whole_word)
  338.             while (len > 0)
  339.               {
  340.             /* If it's preceeded by a word constituent, then no go.  */
  341.             if (beg > 0
  342.                 && WCHAR((unsigned char) matching_line[beg - 1]))
  343.               break;
  344.             /* If it's followed by a word constituent, look for
  345.                a shorter match.  */
  346.             else if (beg + len < maxlen
  347.                 && WCHAR((unsigned char) matching_line[beg + len]))
  348.               /* This is sheer incest. */
  349.               len = re_match_2 (®ex, (unsigned char *) 0, 0,
  350.                         matching_line, maxlen,
  351.                         beg, ®s, beg + len - 1);
  352.             else
  353.               goto succeed;
  354.               }
  355.           else
  356.             goto succeed;
  357.         }
  358.         fail:
  359.           resume = next_line;
  360.           if (resume == search_limit)
  361.         break;
  362.           else
  363.         continue;
  364.         }
  365.  
  366.     succeed:
  367.       /* Print out the matching or nonmatching lines as necessary. */
  368.       if (! nonmatching_lines)
  369.         {
  370.           /* Not -v, so nothing hairy... */
  371.           ++match_count;
  372.  
  373.           /* Print leftover trailing context from last time around.  */
  374.           while (pending_lines && last_match_limit < matching_line)
  375.         {
  376.           last_match_limit += print_line(last_match_limit,
  377.                          initial_line_count++,
  378.                          0);
  379.           --pending_lines;
  380.         }
  381.  
  382.           /* Back up over leading context if necessary. */
  383.           for (i = leading_context;
  384.            i > 0 && matching_line > printed_limit;
  385.            --i)
  386.         {
  387.           while (matching_line > printed_limit
  388.              && (--matching_line)[-1] != '\n')
  389.             ;
  390.           --line_count;
  391.         }
  392.  
  393.           /* If context is enabled, we may have to print a separator. */
  394.           if ((leading_context || trailing_context) && !silent
  395.           && !first_match && (printed_limit_fake
  396.                       || matching_line > printed_limit))
  397.         printf("----------\n");
  398.           first_match = 0;
  399.  
  400.           /* Print the matching line and its leading context. */
  401.           while (matching_line < real_matching_line)
  402.         matching_line += print_line(matching_line, line_count++, 0);
  403.           matching_line += print_line(matching_line, line_count++, 1);
  404.  
  405.           /* If there's trailing context, leave some lines pending until
  406.          next time. */
  407.           pending_lines = trailing_context;
  408.         }
  409.       else if (matching_line == last_match_limit)
  410.         {
  411.           /* In the -v case, this is where we deal with leftover
  412.          trailing context from last time... */
  413.           if (pending_lines > 0)
  414.         {
  415.           --pending_lines;
  416.           print_line(matching_line, line_count, 0);
  417.         }
  418.           ++line_count;
  419.         }
  420.       else if (matching_line > last_match_limit)
  421.         {
  422.           char *start = last_match_limit;
  423.  
  424.           /* Back up over leading context if necessary. */
  425.           for (i = leading_context; start > printed_limit && i; --i)
  426.         {
  427.           while (start > printed_limit && (--start)[-1] != '\n')
  428.             ;
  429.           --initial_line_count;
  430.         }
  431.  
  432.           /* If context is enabled, we may have to print a separator. */
  433.           if ((leading_context || trailing_context) && !silent
  434.           && !first_match && (printed_limit_fake
  435.                       || start > printed_limit))
  436.         printf("----------\n");
  437.           first_match = 0;
  438.  
  439.           /* Print out the presumably matching leading context. */
  440.           while (start < last_match_limit)
  441.         start += print_line(start, initial_line_count++, 0);
  442.  
  443.           /* Print out the nonmatching lines prior to the matching line. */
  444.           while (start < matching_line)
  445.         {
  446.           /* This counts as a "matching line" in -v. */
  447.           ++match_count;
  448.           start += print_line(start, initial_line_count++, 1);
  449.         }
  450.  
  451.           /* Deal with trailing context.  In -v what this means is
  452.          we print the current (matching) line, marked as a non
  453.          matching line.  */
  454.           if (trailing_context)
  455.         {
  456.           print_line(matching_line, line_count, 0);
  457.           pending_lines = trailing_context - 1;
  458.         }
  459.  
  460.           /* Count the current line. */
  461.           ++line_count;
  462.         }
  463.       else
  464.         /* Let us pray this never happens... */
  465.         abort();
  466.  
  467.       /* Resume searching at the beginning of the next line. */
  468.       initial_line_count = line_count;
  469.       resume = next_line;
  470.       last_match_limit = next_line;
  471.  
  472.       if (resume == search_limit)
  473.         break;
  474.     }
  475.  
  476.       /* Restore the saved character. */
  477.       *search_limit = saved_char;
  478.  
  479.       if (! nonmatching_lines)
  480.     {
  481.       while (last_match_limit < search_limit && pending_lines)
  482.         {
  483.           last_match_limit += print_line(last_match_limit,
  484.                          initial_line_count++,
  485.                          0);
  486.           --pending_lines;
  487.         }
  488.     }
  489.       else if (search_limit > last_match_limit)
  490.     {
  491.       char *start = last_match_limit;
  492.  
  493.       /* Back up over leading context if necessary. */
  494.       for (i = leading_context; start > printed_limit && i; --i)
  495.         {
  496.           while (start > printed_limit && (--start)[-1] != '\n')
  497.         ;
  498.           --initial_line_count;
  499.         }
  500.  
  501.       /* If context is enabled, we may have to print a separator. */
  502.       if ((leading_context || trailing_context) && !silent
  503.           && !first_match && (printed_limit_fake
  504.                   || start > printed_limit))
  505.         printf("----------\n");
  506.       first_match = 0;
  507.  
  508.       /* Print out all the nonmatching lines up to the search limit. */
  509.       while (start < last_match_limit)
  510.         start += print_line(start, initial_line_count++, 0);
  511.       while (start < search_limit)
  512.         {
  513.           ++match_count;
  514.           start += print_line(start, initial_line_count++, 1);
  515.         }
  516.  
  517.       pending_lines = trailing_context;
  518.       resume_index = 0;
  519.       retain = bufbytes - (search_limit - buffer);
  520.       continue;
  521.     }
  522.       
  523.       /* Save the trailing end of the buffer for possible use as leading
  524.      context in the future. */
  525.       i = leading_context;
  526.       tmp = search_limit;
  527.       while (tmp > printed_limit && i--)
  528.     while (tmp > printed_limit && (--tmp)[-1] != '\n')
  529.       ;
  530.       resume_index = search_limit - tmp;
  531.       retain = bufbytes - (tmp - buffer);
  532.       if (tmp > printed_limit)
  533.     printed_limit_fake = 1;
  534.     }
  535.  
  536.   return match_count;
  537. }
  538.  
  539. void
  540. usage_and_die()
  541. {
  542.   fprintf(stderr, "\
  543. Usage: %s [-CVbchilnsvwx] [-num] [-A num] [-B num] [-f file]\n\
  544.        [-e] expr [file...]\n", prog);
  545.   exit(ERROR);
  546. }
  547.  
  548. static char version[] = "GNU e?grep, version 1.6";
  549.  
  550. int
  551. main(argc, argv)
  552.      int argc;
  553.      char **argv;
  554. {
  555.   int c;
  556.   int ignore_case = 0;        /* Compile the regexp to ignore case. */
  557.   char *the_regexp = 0;        /* The regular expression. */
  558.   int regexp_len;        /* Length of the regular expression. */
  559.   char *regexp_file = 0;    /* File containing parallel regexps. */
  560.   int count_lines = 0;        /* Display only a count of matching lines. */
  561.   int list_files = 0;        /* Display only the names of matching files. */
  562.   int line_count = 0;        /* Count of matching lines for a file. */
  563.   int matches_found = 0;    /* True if matches were found. */
  564.   char *regex_errmesg;        /* Error message from regex routines. */
  565.   char translate[_NOTCHAR];    /* Translate table for case conversion
  566.                    (needed by the backtracking matcher). */
  567.  
  568.   if (prog = index(argv[0], '/'))
  569.     ++prog;
  570.   else
  571.     prog = argv[0];
  572.  
  573.   opterr = 0;
  574.   while ((c = getopt(argc, argv, "0123456789A:B:CVbce:f:hilnsvwx")) != EOF)
  575.     switch (c)
  576.       {
  577.       case '?':
  578.     usage_and_die();
  579.     break;
  580.  
  581.       case '0':
  582.       case '1':
  583.       case '2':
  584.       case '3':
  585.       case '4':
  586.       case '5':
  587.       case '6':
  588.       case '7':
  589.       case '8':
  590.       case '9':
  591.     trailing_context = 10 * trailing_context + c - '0';
  592.     leading_context = 10 * leading_context + c - '0';
  593.     break;
  594.  
  595.       case 'A':
  596.     if (! sscanf(optarg, "%d", &trailing_context)
  597.         || trailing_context < 0)
  598.       usage_and_die();
  599.     break;
  600.  
  601.       case 'B':
  602.     if (! sscanf(optarg, "%d", &leading_context)
  603.         || leading_context < 0)
  604.       usage_and_die();
  605.     break;
  606.  
  607.       case 'C':
  608.     trailing_context = leading_context = 2;
  609.     break;
  610.  
  611.       case 'V':
  612.     fprintf(stderr, "%s\n", version);
  613.     break;
  614.  
  615.       case 'b':
  616.     byte_count = 1;
  617.     break;
  618.  
  619.       case 'c':
  620.     count_lines = 1;
  621.     silent = 1;
  622.     break;
  623.  
  624.       case 'e':
  625.     /* It doesn't make sense to mix -f and -e. */
  626.     if (regexp_file)
  627.       usage_and_die();
  628.     the_regexp = optarg;
  629.     break;
  630.  
  631.       case 'f':
  632.     /* It doesn't make sense to mix -f and -e. */
  633.     if (the_regexp)
  634.       usage_and_die();
  635.     regexp_file = optarg;
  636.     break;
  637.  
  638.       case 'h':
  639.     no_filenames = 1;
  640.     break;
  641.  
  642.       case 'i':
  643.     ignore_case = 1;
  644.     for (c = 0; c < _NOTCHAR; ++c)
  645.       if (isupper(c))
  646.         translate[c] = tolower(c);
  647.       else
  648.         translate[c] = c;
  649.     regex.translate = translate;
  650.     break;
  651.  
  652.       case 'l':
  653.     list_files = 1;
  654.     silent = 1;
  655.     break;
  656.  
  657.       case 'n':
  658.     line_numbers = 1;
  659.     break;
  660.  
  661.       case 's':
  662.     silent = 1;
  663.     break;
  664.  
  665.       case 'v':
  666.     nonmatching_lines = 1;
  667.     break;
  668.  
  669.       case 'w':
  670.     whole_word = 1;
  671.     break;
  672.  
  673.       case 'x':
  674.     whole_line = 1;
  675.     break;
  676.  
  677.       default:
  678.     /* This can't happen. */
  679.     fprintf(stderr, "%s: getopt(3) let one by!\n", prog);
  680.     usage_and_die();
  681.     break;
  682.       }
  683.  
  684.   /* Set the syntax depending on whether we are EGREP or not. */
  685. #ifdef EGREP
  686.   regsyntax(RE_SYNTAX_EGREP, ignore_case);
  687.   re_set_syntax(RE_SYNTAX_EGREP);
  688. #else
  689.   regsyntax(RE_SYNTAX_GREP, ignore_case);
  690.   re_set_syntax(RE_SYNTAX_GREP);
  691. #endif
  692.  
  693.   /* Compile the regexp according to all the options. */
  694.   if (regexp_file)
  695.     {
  696.       FILE *fp = fopen(regexp_file, "r");
  697.       int len = 256;
  698.       int i = 0;
  699.  
  700.       if (! fp)
  701.     {
  702.       fprintf(stderr, "%s: %s: %s\n", prog, regexp_file,
  703.           sys_errlist[errno]);
  704.       exit(ERROR);
  705.     }
  706.  
  707.       the_regexp = malloc(len);
  708.       while ((c = getc(fp)) != EOF)
  709.     {
  710.       the_regexp[i++] = c;
  711.       if (i == len)
  712.         the_regexp = realloc(the_regexp, len *= 2);
  713.     }
  714.       fclose(fp);
  715.       /* Nuke the concluding newline so we won't match the empty string. */
  716.       if (i > 0 && the_regexp[i - 1] == '\n')
  717.     --i;
  718.       regexp_len = i;
  719.     }
  720.   else if (! the_regexp)
  721.     {
  722.       if (optind >= argc)
  723.     usage_and_die();
  724.       the_regexp = argv[optind++];
  725.       regexp_len = strlen(the_regexp);
  726.     }
  727.   else
  728.     regexp_len = strlen(the_regexp);
  729.   
  730.   if (whole_word || whole_line)
  731.     {
  732.       /* In the whole-word case, we use the pattern:
  733.      (^|[^A-Za-z_])(userpattern)([^A-Za-z_]|$).
  734.      In the whole-line case, we use the pattern:
  735.      ^(userpattern)$.
  736.      BUG: Using [A-Za-z_] is locale-dependent!  */
  737.  
  738.       char *n = malloc(regexp_len + 50);
  739.       int i = 0;
  740.  
  741. #ifdef EGREP
  742.       if (whole_word)
  743.     strcpy(n, "(^|[^A-Za-z_])(");
  744.       else
  745.     strcpy(n, "^(");
  746. #else
  747.       /* Todo:  Make *sure* this is the right syntax.  Down with grep! */
  748.       if (whole_word)
  749.     strcpy(n, "\\(^\\|[^A-Za-z_]\\)\\(");
  750.       else
  751.     strcpy(n, "^\\(");
  752. #endif
  753.       i = strlen(n);
  754.       bcopy(the_regexp, n + i, regexp_len);
  755.       i += regexp_len;
  756. #ifdef EGREP
  757.       if (whole_word)
  758.     strcpy(n + i, ")([^A-Za-z_]|$)");
  759.       else
  760.     strcpy(n + i, ")$");
  761. #else
  762.       if (whole_word)
  763.     strcpy(n + i, "\\)\\([^A-Za-z_]\\|$\\)");
  764.       else
  765.     strcpy(n + i, "\\)$");
  766. #endif
  767.       i += strlen(n + i);
  768.       regcompile(n, i, ®, 1);
  769.     }
  770.   else
  771.     regcompile(the_regexp, regexp_len, ®, 1);
  772.  
  773.   
  774.   if (regex_errmesg = re_compile_pattern(the_regexp, regexp_len, ®ex))
  775.     regerror(regex_errmesg);
  776.   
  777.   /*
  778.     Find the longest metacharacter-free string which must occur in the
  779.     regexpr, before short-circuiting regexecute() with Boyer-Moore-Gosper.
  780.     (Conjecture:  The problem in general is NP-complete.)  If there is no
  781.     such string (like for many alternations), then default to full automaton
  782.     search.  regmust() code and heuristics [see dfa.c] courtesy
  783.     Arthur David Olson.
  784.     */
  785.   if (line_numbers == 0 && nonmatching_lines == 0)
  786.     {
  787.       if (reg.mustn == 0 || reg.mustn == MUST_MAX ||
  788.         index(reg.must, '\0') != reg.must + reg.mustn)
  789.     bmgexec = 0;
  790.       else
  791.     {
  792.       reg.must[reg.mustn] = '\0';
  793.       if (getenv("MUSTDEBUG") != NULL)
  794.         (void) printf("must have: \"%s\"\n", reg.must);
  795.       bmg_setup(reg.must, ignore_case);
  796.       bmgexec = 1;
  797.     }
  798.     }
  799.   
  800.   if (argc - optind < 2)
  801.     no_filenames = 1;
  802.  
  803.   initialize_buffer();
  804.  
  805.   if (argc > optind)
  806.     while (optind < argc)
  807.       {
  808.     bufprev = eof = 0;
  809.     filename = argv[optind++];
  810.     fd = open(filename, 0, 0);
  811.     if (fd < 0)
  812.       {
  813.         fprintf(stderr, "%s: %s: %s\n", prog, filename,
  814.             sys_errlist[errno]);
  815.         error = 1;
  816.         continue;
  817.       }
  818.     if (line_count = grep())
  819.       matches_found = 1;
  820.     close(fd);
  821.     if (count_lines)
  822.       if (!no_filenames)
  823.         printf("%s:%d\n", filename, line_count);
  824.       else
  825.         printf("%d\n", line_count);
  826.     else if (list_files && line_count)
  827.       printf("%s\n", filename);
  828.       }
  829.   else
  830.     {
  831.       if (line_count = grep())
  832.     matches_found = 1;
  833.       if (count_lines)
  834.     printf("%d\n", line_count);
  835.       else if (list_files && line_count)
  836.     printf("<stdin>\n");
  837.     }
  838.  
  839.   if (error)
  840.     exit(ERROR);
  841.   if (matches_found)
  842.     exit(MATCHES_FOUND);
  843.   exit(NO_MATCHES_FOUND);
  844.   return NO_MATCHES_FOUND;
  845. }
  846.  
  847. /* Needed by the regexp routines.  This could be fancier, especially when
  848.    dealing with parallel regexps in files. */
  849. void
  850. regerror(s)
  851.      const char *s;
  852. {
  853.   fprintf(stderr, "%s: %s\n", prog, s);
  854.   exit(ERROR);
  855. }
  856.  
  857. /*
  858.    bmg_setup() and bmg_search() adapted from:
  859.      Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  860.      original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  861.      experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  862.      practical value.  However, to improve for worst case input, integrating
  863.      the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  864.      February 1986) deserves consideration.
  865.  
  866.      James A. Woods                Copyleft (C) 1986, 1988
  867.      NASA Ames Research Center
  868. */
  869.  
  870. char *
  871. execute(r, begin, end, newline, count, try_backref)
  872.   struct regexp *r;
  873.   char *begin;
  874.   char *end;
  875.   int newline;
  876.   int *count;
  877.   int *try_backref;
  878. {
  879.   register char *p, *s;
  880.   char *match;
  881.   char *start = begin;
  882.   char save;            /* regexecute() sentinel */
  883.   int len;
  884.   char *bmg_search();
  885.  
  886.   if (!bmgexec)            /* full automaton search */
  887.     return(regexecute(r, begin, end, newline, count, try_backref));
  888.   else
  889.     {
  890.       len = end - begin; 
  891.       while ((match = bmg_search((unsigned char *) start, len)) != NULL)
  892.     {
  893.       p = match;        /* narrow search range to submatch line */
  894.       while (p > begin && *p != '\n')
  895.         p--;
  896.       s = match;
  897.       while (s < end && *s != '\n')
  898.         s++;
  899.       s++;
  900.  
  901.       save = *s;
  902.       *s = '\0';
  903.       match = regexecute(r, p, s, newline, count, try_backref);
  904.       *s = save;
  905.  
  906.       if (match != NULL)
  907.         return((char *) match);
  908.       else
  909.         {
  910.           start = s;
  911.           len = end - start;
  912.         }
  913.     }
  914.       return(NULL);
  915.     }
  916. }
  917.  
  918. int        delta0[256];
  919. unsigned char   cmap[256];        /* (un)folded characters */
  920. unsigned char    pattern[5000];
  921. int        patlen;
  922.  
  923. char *
  924. bmg_search(buffer, buflen)
  925.   unsigned char *buffer;
  926.   int buflen;
  927. {
  928.   register unsigned char *k, *strend, *s, *buflim;
  929.   register int t;
  930.   int j;
  931.  
  932.   if (patlen > buflen)
  933.     return NULL;
  934.  
  935.   buflim = buffer + buflen;
  936.   if (buflen > patlen * 4)
  937.     strend = buflim - patlen * 4;
  938.   else
  939.     strend = buffer;
  940.  
  941.   s = buffer;
  942.   k = buffer + patlen - 1;
  943.  
  944.   for (;;)
  945.     {
  946.       /* The dreaded inner loop, revisited. */
  947.       while (k < strend && (t = delta0[*k]))
  948.     {
  949.       k += t;
  950.       k += delta0[*k];
  951.       k += delta0[*k];
  952.     }
  953.       while (k < buflim && delta0[*k])
  954.     ++k;
  955.       if (k == buflim)
  956.     break;
  957.     
  958.       j = patlen - 1;
  959.       s = k;
  960.       while (--j >= 0 && cmap[*--s] == pattern[j])
  961.     ;
  962.       /* 
  963.     delta-less shortcut for literati, but 
  964.     short shrift for genetic engineers.
  965.       */
  966.       if (j >= 0)
  967.     k++;
  968.       else         /* submatch */
  969.     return ((char *)k);
  970.     }
  971.   return(NULL);
  972. }
  973.  
  974. int
  975. bmg_setup(pat, folded)            /* compute "boyer-moore" delta table */
  976.   char *pat;
  977.   int folded;
  978. {                    /* ... HAKMEM lives ... */
  979.   int j;
  980.  
  981.   patlen = strlen(pat);
  982.  
  983.   if (folded)                 /* fold case while saving pattern */
  984.     for (j = 0; j < patlen; j++) 
  985.       pattern[j] = (isupper((int) pat[j]) ?
  986.     (char) tolower((int) pat[j]) : pat[j]);
  987.   else
  988.       bcopy(pat, pattern, patlen);
  989.  
  990.   for (j = 0; j < 256; j++)
  991.     {
  992.       delta0[j] = patlen;
  993.       cmap[j] = (char) j;        /* could be done at compile time */
  994.     }
  995.   for (j = 0; j < patlen - 1; j++)
  996.     delta0[pattern[j]] = patlen - j - 1;
  997.   delta0[pattern[patlen - 1]] = 0;
  998.  
  999.   if (folded)
  1000.     {
  1001.       for (j = 0; j < patlen - 1; j++)
  1002.     if (islower((int) pattern[j]))
  1003.       delta0[toupper((int) pattern[j])] = patlen - j - 1;
  1004.     if (islower((int) pattern[patlen - 1]))
  1005.       delta0[toupper((int) pattern[patlen - 1])] = 0;
  1006.       for (j = 'A'; j <= 'Z'; j++)
  1007.     cmap[j] = (char) tolower((int) j);
  1008.     }
  1009. }
  1010.